package com.algrithom.tree.dictree;

import java.util.Arrays;

/**
 * 820. 单词的压缩编码
 */
class Solution2 {
    
    public static void main(String[] args){
        String[] words = {"time","me","bell"};
        System.out.println(minimumLengthEncoding(words));
    }
    
    public static int minimumLengthEncoding(String[] words){
        int len = 0;
        Trie trie = new Trie();
        // 先对单词列表根据单词长度由长到短排序
        Arrays.sort(words,(s1,s2) -> s2.length() - s1.length());
        // 单词插入trie，返回该单词增加的编码长度
        for (String word : words) {
            len += trie.insert(word);
        }
        return len;
    }
}

/**
 * 定义tire
 */
class Trie {
    
    TrieNode root;
    
    public Trie(){
        root = new TrieNode();
    }
    
    public int insert(String word){
        TrieNode cur = root;
        boolean isNew = false;
        // 倒着插入单词
        for (int i = word.length() - 1; i >= 0; i--) {
            int c = word.charAt(i) - 'a';
            if (cur.children[c] == null) {
                isNew = true;
                cur.children[c] = new TrieNode();
            }
            cur = cur.children[c];
        }
        // 如果是新单词的话编码长度增加新单词的长度+1，否则不变。
        return isNew ? word.length() + 1 : 0;
    }
}

class TrieNode {
    
    private static final int TWENTY_SIX = 26;
    
    TrieNode[] children = new TrieNode[TWENTY_SIX];
    
    public TrieNode(){}
}
